package com.faiz.algorithm;

import java.util.Arrays;

public class MergeSort {

    public int[] mergerSort(int[] nums) {

        int[] arr = Arrays.copyOf(nums, nums.length);
        int length = arr.length;
        if (length < 2) {
            return arr;
        }

        int median = (int) Math.floor(length / 2.0);

        int[] left = mergerSort(Arrays.copyOfRange(nums, 0, median));
        int[] right = mergerSort(Arrays.copyOfRange(nums, median, length));

        return merge(left, right);
    }

    private int[] merge(int[] left, int[] right) {
        int leftLength = left.length;
        int rightLength = right.length;

        int[] mergeArr = new int[leftLength + rightLength];

        int lIndex = 0, rIndex = 0, index = 0;
        while (lIndex < leftLength && rIndex < rightLength) {
            int tmp;
            if (left[lIndex] <= right[rIndex]) {
                tmp = left[lIndex];
                lIndex++;
            } else {
                tmp = right[rIndex];
                rIndex++;
            }
            mergeArr[index] = tmp;
            index++;
        }

        // 这里是要将所有为经过比价的元素从left或right中取出
        while (index < mergeArr.length) {
            while (lIndex < leftLength) {
                mergeArr[index] = left[lIndex];
                lIndex++;
                index++;
            }

            while (rIndex < rightLength) {
                mergeArr[index] = right[rIndex];
                rIndex++;
                index++;
            }
        }
        return mergeArr;
    }

    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        int[] nums = {2, 3, 4, 5, 1, 1, 1, 2, 5, 4, 5, 2};
        System.out.println(Arrays.toString(mergeSort.mergerSort(nums)));
    }
}
